The traditional branching strategies of Maximum Common induced Subgraph (MCS) problem rely on the static properties of graphs and lack learning information about historical searches. In order to solve these problems, a branching strategy based on vertex conflict learning was proposed. Firstly, the reduction value of the upper bound was used as the reward to the branch node for completing a matching action. Secondly, when the optimal solution was updated, the optimal solution obtained actually was the result of continuous inference of the branch nodes. Therefore, the appropriate rewards were given to the branch nodes on the complete search path to strengthen the positive effect of these vertices on search. Finally, the value function of matching action was designed, and the vertices with the maximum cumulative rewards would be selected as new branch nodes. On the basis of Maximum common induced subgraph Split (McSplit) algorithm, an improved McSplit Reinforcement Learning and Routing (McSplitRLR) algorithm combined with the new branching strategy was completed. Experimental results show that, with the same computer and solution time limit, excluding the simple instances solved by all comparison algorithms within 10 seconds, compared to the state-of-the-art algorithms of McSplit and McSplit Solution-Biased Search (McSplitSBS), McSplitRLR solves 109 and 33 more hard instances respectively, and the solution rate increases by 5.6% and 1.6% respectively.

The limited number and high similarity of learning clauses lead to limited historical information and imbalanced search tree. In order to solve the problems, a dynamic branching strategy of award and punishment was proposed. Firstly, the variables of every unit propagation were punished. Different penalty functions were established according to whether the variable generated a conflict and the conflict interval. Then, in the learning phase, the positive variables for the conflict were found according to the learning clauses, and their activities were nonlinearly increased. Finally, the variable with the maximum activity was chosen as the new branching variable. On the basis of the glucose3.0 algorithm, an improved dynamic algorithm of award and punishment named Award and Punishment 7 (AP7) was completed. The experimental results show that, compared with the glucose3.0 algorithm, the rate of cutting branches of AP7 algorithm is improved by 14.2%-29.3%, and that of a few examples is improved up to 51%. The running time of the improved AP7 algorithm is shortened more than 7% compared with the glucose3.0 algorithm. The branching strategy can efficiently reduce the size of search tree, make the search tree more balanced and reduce the computation time.

To effectively utilize the depth information from RGB-D (Red Green Blue and Depth) images and enhance the scale invariance and rotation invariance of BRISK (Binary Robust Invariant Scalable Keypoints) algorithm, an improved BRISK algorithm combined with depth information was proposed. Firstly, the keypoints were detected by the FAST (Features from Accelerated Segment Test) algorithm and their Harris corner response values were computed. Then, the entire image was divided into the same size grids, and the keypoint with the maximum Harris corner response value was reserved by each grid. Next, the scale factor of the keypoint was directly computed with the depth information of the image. Finally, the intensity centroid of the circle centered on the keypoint was calculated, and the orientation of keypoint was computed by the offset from its intensity centroid. The comparison experiment analysis of several algorithms on the scale invariance and rotation invariance was performed. The experimental results show that, compared with the BRISK algorithm, the number of correctly matched keypoints of the improved algorithm improves by more than 90% when the image's scale is changed and raises by at least 70% when the image is rotated.